Estas notas estan basadas en el libro R for Data Science de Garrett Grolemund y Hadley Wickham

Modelo Lineal: Enfoque de Machine Learning

library(tidyverse)
library(modelr)
library(plotly)
options(na.action = na.warn)

Usualmente se observa el enfoque "estadístico para hallar las estimaciones de los parámetros en un modelo lineal. Obtenemos los valores con las siguientes fórmulas:

\(\hat{\beta_0} = \overline{Y} - \hat{\beta_1} \cdot \overline{X}\)

\(\hat{\beta_1} = \frac{\sum{(X_i - \overline{X})(Y_i - \overline{Y})}}{\sum{(X_i - \overline{X})^2}}\)

En este caso vamos a desarrollar otra manera de hallar los valores de estos parámetros, mediante un enfoque de optimización.

datos sim1

El paquete modlr viene con un set de datos de juguete llamado sim1

ggplot(sim1, aes(x, y)) + 
  geom_point() +
  theme_bw()

Se puede ver un patrón fuerte en los datos. Pareciera que el modelo lineal y = a_0 + a_1 * x puede ser apropiado para modelar estos datos

Modelos al azar

Para empezar, generemos aleatoriamente varios modelos lineales para ver qué forma tienen. Para eso, podemos usar geom_abline () que toma una pendiente e intercepto como parámetros.

models <- tibble(
  a1 = runif(250, -20, 40), # Función para tomar valores al azar de una distribución uniforme
  a2 = runif(250, -5, 5) # Función para tomar valores al azar de una distribución uniforme
)

ggplot(sim1, aes(x, y)) + 
  geom_abline(aes(intercept = a1, slope = a2), data = models, alpha = 1/4) +
  geom_point() +
  theme_bw()

A simple vista podemos apreciar que algunos modelos son mejores que otros. Pero necesitamos una forma de cuantificar cuales son los mejores modelos.

Distancias

Una forma de definir mejor es pensar en aquel modelo que minimiza la distancia vertical de la recta (el modelo) con cada punto:

Para eso, elijamos un modelo cualquiera:

\[ y= 7 + 1.5*x\]

dist1 <- sim1 %>% 
  mutate(
    dodge = rep(c(-1, 0, 1) / 20, 10),
    x1 = x + dodge, # para que se vean mejor las distancias, corremos un poquito cada punto sobre el eje x
    pred = 7 + x1 * 1.5
  )

ggplot(dist1, aes(x1, y)) + 
  geom_abline(intercept = 7, slope = 1.5, colour = "grey40") +
  geom_point(colour = "grey40") +
  geom_linerange(aes(ymin = y, ymax = pred), colour = "#3366FF") +
  theme_bw()

La distancia de cada punto a la recta es la diferencia entre lo que predice nuestro modelo y el valor real

Función de Modelo

Para computar la distancia, primero necesitamos una función que permita representar a cualquier modelo.

Ejercicio

Crear una función que reciba un vector con los parametros del modelo, y el set de datos, y genere la predicción:

model1 <- function(a, data) {
   a[1] + data$x * a[2]
   }
model1(c(7, 1.5), sim1)
 [1]  8.5  8.5  8.5 10.0 10.0 10.0 11.5 11.5 11.5 13.0 13.0 13.0 14.5 14.5 14.5 16.0 16.0 16.0 17.5 17.5 17.5 19.0 19.0 19.0 20.5 20.5 20.5
[28] 22.0 22.0 22.0

Necesitamos una forma de cuantificar el error de predicción de nuestro modelo en todas las observaciones y resumirlo en única métrica. Esta será la función objetivo que buscaremos minimizar.

Una de las formas de hacerlo es con el error cuadrático medio (ECM)

Ejercicio 2

Necesitamos una función, que reciba un vector con los parametros del modelo y el set de datos, que calcule el promedio de los errores cuadráticos (ECM)

\[ECM = \frac{\sum_i^n{(\hat{y_i} - y_i)^2}}{n}\]

measure_distance <- function(mod, data) {
 diff <- data$y - model1(mod, data)
 mean(diff ^ 2)
   }
measure_distance(c(7, 1.5), sim1)
[1] 7.103355

Evaluando los modelos aleatorios

Ahora podemos calcular el ECM para todos los modelos del dataframe models. Para eso utilizamos el paquete purrr, para ejecutar varias veces la misma función sobre varios elementos.

MAP1

Nosotros tenemos que pasar pasar los valores de a1 y a2 (dos parámetros –> map2), pero como nuestra función toma sólo uno (el vector a), nos armamos una función de ayuda para wrapear a1 y a2

sim1_dist <- function(a1, a2) {
  measure_distance(c(a1, a2), sim1)
}

models <- models %>% 
  mutate(dist = purrr::map2_dbl(a1, a2, sim1_dist))
models

A continuación, superpongamos los 10 mejores modelos a los datos. Coloreamos los modelos por -dist: esta es una manera fácil de asegurarse de que los mejores modelos (es decir, los que tienen la menor distancia) obtengan los colores más brillantes.

ggplot(sim1, aes(x, y)) + 
  geom_point(size = 2, colour = "grey30") + 
  geom_abline(data = filter(models, rank(dist) <= 10),
              aes(intercept = a1, slope = a2, colour = -dist)) +
  theme_bw()

NA

También podemos pensar en estos modelos como observaciones y visualizar con un gráfico de dispersión de a1 vsa2, nuevamente coloreado por -dist. Ya no podemos ver directamente cómo se compara el modelo con los datos, pero podemos ver muchos modelos a la vez. Nuevamente, destacamos los 10 mejores modelos, esta vez dibujando círculos rojos debajo de ellos.

ggplot(models, aes(a1, a2)) +
  geom_point(data = filter(models, rank(dist) <= 10), size = 4, colour = "red") +
  geom_point(aes(colour = -dist))  +
  theme_bw()

Superficie del ECM

Podemos pasar del gráfico de la grilla de puntos a graficar los mismos datos en tres dimensiones. En el plano xy tendremos a ambos parámetros y en el eje z observamos el valor del del error cuadractico medio (ECM).

Notemos que ya no estamos trabajando con la distancia sino que estamos graficando la superficie del ECM como función de ambos parametros.

Por la fórmula del ECM esta superficie es convexa y presenta un mínimo global.

# Matriz para el grafico
rss_matrix <- matrix(models_grid[["dist"]],nrow = length(b1),ncol = length(b1), byrow = TRUE)

# Grafico usando plotly
rss_graph = plot_ly(x=b0, y=b1, z=rss_matrix) %>% add_surface(contours = list(
  z = list(
    show=TRUE,
    usecolormap=TRUE,
    highlightcolor="#ff0000",
    project=list(z=TRUE)
  )
), reversescale=TRUE)  %>%
  layout(
    title = "Superficie del ECM",
    scene = list(
      xaxis = list(title = "a0"),
      yaxis = list(title = "a1"),
      zaxis = list(title = "RSS")
    ))

rss_graph

Óptimo por métodos numéricos

Podríamos ir haciendo la cuadrícula más fina y fina hasta que nos centramos en el mejor modelo. Pero hay mejores formas de abordar ese problema como herramientas de optimización numéricas. Algunas de ellas son:

  • Búsqueda Newton-Raphson.
  • Gradient Descent

La intuición de estas dos herramientas es bastante simple: Se elige un punto de partida en la superficie de la función objetivo y se busca la pendiente más inclinada. Luego, desciende por esa pendiente un poco, y se repite una y otra vez, hasta alcanzar la condición de corte.

En R, podemos utilizar la función optim (). Cuenta con los siguientes parámetros:

  • par: vector de puntos iniciales. Elegimos el origen por poner cualquier cosa
  • fn: función objetivo, y los parámetros que nuestra función necesita (data)
# Corremos la optimizacion
best <- optim(c(0, 0), measure_distance, data = sim1)

best
$par
[1] 4.222248 2.051204

$value
[1] 4.529154

$counts
function gradient 
      77       NA 

$convergence
[1] 0

$message
NULL
```r
# Obtenemos los mejores parametros
best$par

<!-- rnb-source-end -->

<!-- rnb-output-begin eyJkYXRhIjoiWzFdIDQuMjIyMjQ4IDIuMDUxMjA0XG4ifQ== -->

[1] 4.222248 2.051204




<!-- rnb-output-end -->

<!-- rnb-source-begin eyJkYXRhIjoiYGBgclxuYGBgclxuIyBHcmFmaWNhbW9zIGxhIGxpbmVhIGRlIGxvcyBtZWpvcmVzIHBhcmFtZXRyb3NcbmdncGxvdChzaW0xLCBhZXMoeCwgeSkpICsgXG4gIGdlb21fcG9pbnQoc2l6ZSA9IDIsIGNvbG91ciA9IFxcZ3JleTMwXFwpICsgXG4gIGdlb21fYWJsaW5lKGludGVyY2VwdCA9IGJlc3QkcGFyWzFdLCBzbG9wZSA9IGJlc3QkcGFyWzJdLCBjb2xvcj1cXGZpcmVicmlja1xcKSArXG4gIHRoZW1lX2J3KClcbmBgYFxuYGBgIn0= -->

```r
```r
# Graficamos la linea de los mejores parametros
ggplot(sim1, aes(x, y)) + 
  geom_point(size = 2, colour = \grey30\) + 
  geom_abline(intercept = best$par[1], slope = best$par[2], color=\firebrick\) +
  theme_bw()

```

LS0tCnRpdGxlOiAiUmVncmVzacOzbiBMaW5lYWwgU2ltcGxlOiBFbmZvcXVlIE1hY2hpbmUgTGVhcm5pbmciCmF1dGhvcjogIkp1YW4gQmFycmlvbGEgeSBTb2bDrWEgUGVyaW5pIgpkYXRlOiAiMjYgZGUgU2VwdGllbWJyZSBkZSAyMDIwIgpvdXRwdXQ6CiAgaHRtbF9ub3RlYm9vazoKICAgIHRoZW1lOiBzcGFjZWxhYgogICAgdG9jOiB5ZXMKICAgIHRvY19mbG9hdDogeWVzCiAgICBkZl9wcmludDogcGFnZWQKLS0tCgpFc3RhcyBub3RhcyBlc3RhbiBiYXNhZGFzIGVuIGVsIGxpYnJvIFtSIGZvciBEYXRhIFNjaWVuY2VdKGh0dHA6Ly9yNGRzLmhhZC5jby5ueikgZGUgR2FycmV0dCBHcm9sZW11bmQgeSBIYWRsZXkgV2lja2hhbQoKIyBNb2RlbG8gTGluZWFsOiBFbmZvcXVlIGRlIE1hY2hpbmUgTGVhcm5pbmcKCmBgYHtyIHNldHVwLCBtZXNzYWdlID0gRkFMU0V9CmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KG1vZGVscikKbGlicmFyeShwbG90bHkpCm9wdGlvbnMobmEuYWN0aW9uID0gbmEud2FybikKYGBgCgpVc3VhbG1lbnRlIHNlIG9ic2VydmEgZWwgZW5mb3F1ZSAiZXN0YWTDrXN0aWNvIHBhcmEgaGFsbGFyIGxhcyBlc3RpbWFjaW9uZXMgZGUgbG9zIHBhcsOhbWV0cm9zIGVuIHVuIG1vZGVsbyBsaW5lYWwuIE9idGVuZW1vcyBsb3MgdmFsb3JlcyBjb24gbGFzIHNpZ3VpZW50ZXMgZsOzcm11bGFzOgoKJFxoYXR7XGJldGFfMH0gPSBcb3ZlcmxpbmV7WX0gLSBcaGF0e1xiZXRhXzF9IFxjZG90IFxvdmVybGluZXtYfSQKCiRcaGF0e1xiZXRhXzF9ID0gXGZyYWN7XHN1bXsoWF9pIC0gXG92ZXJsaW5le1h9KShZX2kgLSBcb3ZlcmxpbmV7WX0pfX17XHN1bXsoWF9pIC0gXG92ZXJsaW5le1h9KV4yfX0kCgpFbiBlc3RlIGNhc28gdmFtb3MgYSBkZXNhcnJvbGxhciBvdHJhIG1hbmVyYSBkZSBoYWxsYXIgbG9zIHZhbG9yZXMgZGUgZXN0b3MgcGFyw6FtZXRyb3MsIG1lZGlhbnRlIHVuIGVuZm9xdWUgZGUgb3B0aW1pemFjacOzbi4KCiMjIGRhdG9zIHNpbTEKCkVsIHBhcXVldGUgbW9kbHIgdmllbmUgY29uIHVuIHNldCBkZSBkYXRvcyBkZSBqdWd1ZXRlIGxsYW1hZG8gc2ltMQoKYGBge3J9CmdncGxvdChzaW0xLCBhZXMoeCwgeSkpICsgCiAgZ2VvbV9wb2ludCgpICsKICB0aGVtZV9idygpCmBgYAoKU2UgcHVlZGUgdmVyIHVuIHBhdHLDs24gZnVlcnRlIGVuIGxvcyBkYXRvcy4gUGFyZWNpZXJhIHF1ZSBlbCBtb2RlbG8gbGluZWFsIGB5ID0gYV8wICsgYV8xICogeGAgcHVlZGUgc2VyIGFwcm9waWFkbyBwYXJhIG1vZGVsYXIgZXN0b3MgZGF0b3MgCgojIyBNb2RlbG9zIGFsIGF6YXIKClBhcmEgZW1wZXphciwgZ2VuZXJlbW9zIGFsZWF0b3JpYW1lbnRlIHZhcmlvcyBtb2RlbG9zIGxpbmVhbGVzIHBhcmEgdmVyIHF1w6kgZm9ybWEgdGllbmVuLiBQYXJhIGVzbywgcG9kZW1vcyB1c2FyIGBnZW9tX2FibGluZSAoKWAgcXVlIHRvbWEgdW5hIHBlbmRpZW50ZSBlIGludGVyY2VwdG8gY29tbyBwYXLDoW1ldHJvcy4gCgpgYGB7cn0KbW9kZWxzIDwtIHRpYmJsZSgKICBhMSA9IHJ1bmlmKDI1MCwgLTIwLCA0MCksICMgRnVuY2nDs24gcGFyYSB0b21hciB2YWxvcmVzIGFsIGF6YXIgZGUgdW5hIGRpc3RyaWJ1Y2nDs24gdW5pZm9ybWUKICBhMiA9IHJ1bmlmKDI1MCwgLTUsIDUpICMgRnVuY2nDs24gcGFyYSB0b21hciB2YWxvcmVzIGFsIGF6YXIgZGUgdW5hIGRpc3RyaWJ1Y2nDs24gdW5pZm9ybWUKKQoKZ2dwbG90KHNpbTEsIGFlcyh4LCB5KSkgKyAKICBnZW9tX2FibGluZShhZXMoaW50ZXJjZXB0ID0gYTEsIHNsb3BlID0gYTIpLCBkYXRhID0gbW9kZWxzLCBhbHBoYSA9IDEvNCkgKwogIGdlb21fcG9pbnQoKSArCiAgdGhlbWVfYncoKQpgYGAKCgpBIHNpbXBsZSB2aXN0YSBwb2RlbW9zIGFwcmVjaWFyIHF1ZSBhbGd1bm9zIG1vZGVsb3Mgc29uIG1lam9yZXMgcXVlIG90cm9zLiBQZXJvIG5lY2VzaXRhbW9zIHVuYSBmb3JtYSBkZSBjdWFudGlmaWNhciBjdWFsZXMgc29uIGxvcyBfbWVqb3Jlc18gbW9kZWxvcy4gCgojIyBEaXN0YW5jaWFzCgpVbmEgZm9ybWEgZGUgZGVmaW5pciBfbWVqb3JfIGVzIHBlbnNhciBlbiBhcXVlbCBtb2RlbG8gcXVlIG1pbmltaXphIGxhIGRpc3RhbmNpYSB2ZXJ0aWNhbCBkZSBsYSByZWN0YSAoZWwgbW9kZWxvKSBjb24gY2FkYSBwdW50bzoKClBhcmEgZXNvLCBlbGlqYW1vcyB1biBtb2RlbG8gY3VhbHF1aWVyYToKCiQkIHk9IDcgKyAxLjUqeCQkCgoKYGBge3J9CmRpc3QxIDwtIHNpbTEgJT4lIAogIG11dGF0ZSgKICAgIGRvZGdlID0gcmVwKGMoLTEsIDAsIDEpIC8gMjAsIDEwKSwKICAgIHgxID0geCArIGRvZGdlLCAjIHBhcmEgcXVlIHNlIHZlYW4gbWVqb3IgbGFzIGRpc3RhbmNpYXMsIGNvcnJlbW9zIHVuIHBvcXVpdG8gY2FkYSBwdW50byBzb2JyZSBlbCBlamUgeAogICAgcHJlZCA9IDcgKyB4MSAqIDEuNQogICkKCmdncGxvdChkaXN0MSwgYWVzKHgxLCB5KSkgKyAKICBnZW9tX2FibGluZShpbnRlcmNlcHQgPSA3LCBzbG9wZSA9IDEuNSwgY29sb3VyID0gImdyZXk0MCIpICsKICBnZW9tX3BvaW50KGNvbG91ciA9ICJncmV5NDAiKSArCiAgZ2VvbV9saW5lcmFuZ2UoYWVzKHltaW4gPSB5LCB5bWF4ID0gcHJlZCksIGNvbG91ciA9ICIjMzM2NkZGIikgKwogIHRoZW1lX2J3KCkKYGBgCgoKTGEgZGlzdGFuY2lhIGRlIGNhZGEgcHVudG8gYSBsYSByZWN0YSBlcyBsYSBkaWZlcmVuY2lhIGVudHJlIGxvIHF1ZSBwcmVkaWNlIG51ZXN0cm8gbW9kZWxvIHkgZWwgdmFsb3IgcmVhbAoKIyMgRnVuY2nDs24gZGUgTW9kZWxvCgpQYXJhIGNvbXB1dGFyIGxhIGRpc3RhbmNpYSwgcHJpbWVybyBuZWNlc2l0YW1vcyB1bmEgZnVuY2nDs24gcXVlIHBlcm1pdGEgcmVwcmVzZW50YXIgYSBjdWFscXVpZXIgbW9kZWxvLgoKIyMjIEVqZXJjaWNpbwoKQ3JlYXIgdW5hIGZ1bmNpw7NuIHF1ZSByZWNpYmEgdW4gdmVjdG9yIGNvbiBsb3MgcGFyYW1ldHJvcyBkZWwgbW9kZWxvLCB5IGVsIHNldCBkZSBkYXRvcywgeSBnZW5lcmUgbGEgcHJlZGljY2nDs246CiAgCmBgYHtyfQptb2RlbDEgPC0gZnVuY3Rpb24oYSwgZGF0YSkgewogICBhWzFdICsgZGF0YSR4ICogYVsyXQogICB9Cm1vZGVsMShjKDcsIDEuNSksIHNpbTEpCmBgYAoKTmVjZXNpdGFtb3MgdW5hIGZvcm1hIGRlIGN1YW50aWZpY2FyIGVsIGVycm9yIGRlIHByZWRpY2Npw7NuIGRlIG51ZXN0cm8gbW9kZWxvIGVuIHRvZGFzIGxhcyBvYnNlcnZhY2lvbmVzIHkgcmVzdW1pcmxvIGVuIMO6bmljYSBtw6l0cmljYS4KRXN0YSBzZXLDoSBsYSBmdW5jacOzbiBvYmpldGl2byBxdWUgYnVzY2FyZW1vcyBtaW5pbWl6YXIuIAoKVW5hIGRlIGxhcyBmb3JtYXMgZGUgaGFjZXJsbyBlcyBjb24gZWwgZXJyb3IgY3VhZHLDoXRpY28gbWVkaW8gKEVDTSkKCiMjIyBFamVyY2ljaW8gMgoKTmVjZXNpdGFtb3MgdW5hIGZ1bmNpw7NuLCBxdWUgcmVjaWJhIHVuIHZlY3RvciBjb24gbG9zIHBhcmFtZXRyb3MgZGVsIG1vZGVsbyB5IGVsIHNldCBkZSBkYXRvcywgcXVlIGNhbGN1bGUgZWwgcHJvbWVkaW8gZGUgbG9zIGVycm9yZXMgY3VhZHLDoXRpY29zIChFQ00pCiAKJCRFQ00gPSBcZnJhY3tcc3VtX2lebnsoXGhhdHt5X2l9IC0geV9pKV4yfX17bn0kJAoKYGBge3J9Cm1lYXN1cmVfZGlzdGFuY2UgPC0gZnVuY3Rpb24obW9kLCBkYXRhKSB7CiBkaWZmIDwtIGRhdGEkeSAtIG1vZGVsMShtb2QsIGRhdGEpCiBtZWFuKGRpZmYgXiAyKQogICB9Cm1lYXN1cmVfZGlzdGFuY2UoYyg3LCAxLjUpLCBzaW0xKQpgYGAKCiMjIEV2YWx1YW5kbyBsb3MgbW9kZWxvcyBhbGVhdG9yaW9zCgpBaG9yYSBwb2RlbW9zIGNhbGN1bGFyIGVsIF9fRUNNX18gcGFyYSB0b2RvcyBsb3MgbW9kZWxvcyBkZWwgZGF0YWZyYW1lIF9tb2RlbHNfLiBQYXJhIGVzbyB1dGlsaXphbW9zIGVsIHBhcXVldGUgX19wdXJycl9fLCBwYXJhIGVqZWN1dGFyIHZhcmlhcyB2ZWNlcyBsYSBtaXNtYSBmdW5jacOzbiBzb2JyZSB2YXJpb3MgZWxlbWVudG9zLiAKCiMjIyBNQVBeW2Jhc2FkbyBlbiBodHRwczovL2plbm55YmMuZ2l0aHViLmlvL3B1cnJyLXR1dG9yaWFsL2xzMDNfbWFwLWZ1bmN0aW9uLXN5bnRheC5odG1sXQoKTm9zb3Ryb3MgdGVuZW1vcyBxdWUgcGFzYXIgcGFzYXIgbG9zIHZhbG9yZXMgZGUgYTEgeSBhMiAoZG9zIHBhcsOhbWV0cm9zIC0tPiBtYXAyKSwgcGVybyBjb21vIG51ZXN0cmEgZnVuY2nDs24gdG9tYSBzw7NsbyB1bm8gKGVsIHZlY3RvciBhKSwgbm9zIGFybWFtb3MgdW5hIGZ1bmNpw7NuIGRlIGF5dWRhIHBhcmEgd3JhcGVhciBhMSB5IGEyCgoKYGBge3J9CnNpbTFfZGlzdCA8LSBmdW5jdGlvbihhMSwgYTIpIHsKICBtZWFzdXJlX2Rpc3RhbmNlKGMoYTEsIGEyKSwgc2ltMSkKfQoKbW9kZWxzIDwtIG1vZGVscyAlPiUgCiAgbXV0YXRlKGRpc3QgPSBwdXJycjo6bWFwMl9kYmwoYTEsIGEyLCBzaW0xX2Rpc3QpKQptb2RlbHMKYGBgCgoKQSBjb250aW51YWNpw7NuLCBzdXBlcnBvbmdhbW9zIGxvcyAxMCBtZWpvcmVzIG1vZGVsb3MgYSBsb3MgZGF0b3MuIENvbG9yZWFtb3MgbG9zIG1vZGVsb3MgcG9yIGAtZGlzdGA6IGVzdGEgZXMgdW5hIG1hbmVyYSBmw6FjaWwgZGUgYXNlZ3VyYXJzZSBkZSBxdWUgbG9zIG1lam9yZXMgbW9kZWxvcyAoZXMgZGVjaXIsIGxvcyBxdWUgdGllbmVuIGxhIG1lbm9yIGRpc3RhbmNpYSkgb2J0ZW5nYW4gbG9zIGNvbG9yZXMgbcOhcyBicmlsbGFudGVzLgoKCmBgYHtyfQpnZ3Bsb3Qoc2ltMSwgYWVzKHgsIHkpKSArIAogIGdlb21fcG9pbnQoc2l6ZSA9IDIsIGNvbG91ciA9ICJncmV5MzAiKSArIAogIGdlb21fYWJsaW5lKGRhdGEgPSBmaWx0ZXIobW9kZWxzLCByYW5rKGRpc3QpIDw9IDEwKSwKICAgICAgICAgICAgICBhZXMoaW50ZXJjZXB0ID0gYTEsIHNsb3BlID0gYTIsIGNvbG91ciA9IC1kaXN0KSkgKwogIHRoZW1lX2J3KCkKICAgICAgICAgICAgICAKYGBgCgoKVGFtYmnDqW4gcG9kZW1vcyBwZW5zYXIgZW4gZXN0b3MgbW9kZWxvcyBjb21vIG9ic2VydmFjaW9uZXMgeSB2aXN1YWxpemFyIGNvbiB1biBncsOhZmljbyBkZSBkaXNwZXJzacOzbiBkZSBgYTFgIHZzYCBhMmAsIG51ZXZhbWVudGUgY29sb3JlYWRvIHBvciBgLWRpc3RgLiBZYSBubyBwb2RlbW9zIHZlciBkaXJlY3RhbWVudGUgY8OzbW8gc2UgY29tcGFyYSBlbCBtb2RlbG8gY29uIGxvcyBkYXRvcywgcGVybyBwb2RlbW9zIHZlciBtdWNob3MgbW9kZWxvcyBhIGxhIHZlei4gTnVldmFtZW50ZSwgZGVzdGFjYW1vcyBsb3MgMTAgbWVqb3JlcyBtb2RlbG9zLCBlc3RhIHZleiBkaWJ1amFuZG8gY8OtcmN1bG9zIHJvam9zIGRlYmFqbyBkZSBlbGxvcy4KCmBgYHtyfQpnZ3Bsb3QobW9kZWxzLCBhZXMoYTEsIGEyKSkgKwogIGdlb21fcG9pbnQoZGF0YSA9IGZpbHRlcihtb2RlbHMsIHJhbmsoZGlzdCkgPD0gMTApLCBzaXplID0gNCwgY29sb3VyID0gInJlZCIpICsKICBnZW9tX3BvaW50KGFlcyhjb2xvdXIgPSAtZGlzdCkpICArCiAgdGhlbWVfYncoKQpgYGAKCiMjIEdyaWQgc2VhcmNoCgpFbiBsdWdhciBkZSBwcm9iYXIgbXVjaG9zIG1vZGVsb3MgYWxlYXRvcmlvcywgcG9kcsOtYW1vcyBzZXIgbcOhcyBzaXN0ZW3DoXRpY29zIHkgZ2VuZXJhciB1bmEgY3VhZHLDrWN1bGEgZGUgcHVudG9zIHVuaWZvcm1lbWVudGUgZXNwYWNpYWRhIChlc3RvIHNlIGRlbm9taW5hIGdyaWQgc2VhcmNoKS4gRWxlZ2ltb3MgbG9zIHBhcsOhbWV0cm9zIGRlIGxhIGdyaWxsYSBhcHJveGltYWRhbWVudGUgbWlyYW5kbyBkw7NuZGUgZXN0YWJhbiBsb3MgbWVqb3JlcyBtb2RlbG9zIGVuIGVsIGdyw6FmaWNvIGFudGVyaW9yLgoKCmBgYHtyfQojIENyZWFyIGxhIGdyaWxsYQpncmlkIDwtIGV4cGFuZC5ncmlkKAogIGExID0gc2VxKC01LCAyMCwgbGVuZ3RoID0gMjUpLAogIGEyID0gc2VxKDEsIDMsIGxlbmd0aCA9IDI1KQogICkgJT4lIAogICMgQ2FsY3VsYXIgbGEgZGlzdGFuY2lhCiAgbXV0YXRlKGRpc3QgPSBwdXJycjo6bWFwMl9kYmwoYTEsIGEyLCBzaW0xX2Rpc3QpKQoKZ3JpZCAlPiUgCiAgZ2dwbG90KGFlcyhhMSwgYTIpKSArCiAgZ2VvbV9wb2ludChkYXRhID0gZmlsdGVyKGdyaWQsIHJhbmsoZGlzdCkgPD0gMTApLCBzaXplID0gNCwgY29sb3VyID0gInJlZCIpICsKICBnZW9tX3BvaW50KGFlcyhjb2xvdXIgPSAtZGlzdCkpICsKICB0aGVtZV9idygpCmBgYAoKQ3VhbmRvIHN1cGVycG9uZW1vcyBsb3MgMTAgbWVqb3JlcyBtb2RlbG9zIGVuIGxvcyBkYXRvcyBvcmlnaW5hbGVzLCB0b2RvcyBzZSB2ZW4gYmFzdGFudGUgYmllbjoKCmBgYHtyfQpnZ3Bsb3Qoc2ltMSwgYWVzKHgsIHkpKSArIAogIGdlb21fcG9pbnQoc2l6ZSA9IDIsIGNvbG91ciA9ICJncmV5MzAiKSArIAogIGdlb21fYWJsaW5lKAogICAgYWVzKGludGVyY2VwdCA9IGExLCBzbG9wZSA9IGEyLCBjb2xvdXIgPSAtZGlzdCksIAogICAgZGF0YSA9IGZpbHRlcihncmlkLCByYW5rKGRpc3QpIDw9IDEwKSkgKwogIHRoZW1lX2J3KCkKYGBgCgojIyBTdXBlcmZpY2llIGRlbCBFQ00KClBvZGVtb3MgcGFzYXIgZGVsIGdyw6FmaWNvIGRlIGxhIGdyaWxsYSBkZSBwdW50b3MgYSBncmFmaWNhciBsb3MgbWlzbW9zIGRhdG9zIGVuIHRyZXMgZGltZW5zaW9uZXMuIEVuIGVsIHBsYW5vICp4eSogdGVuZHJlbW9zIGEgYW1ib3MgcGFyw6FtZXRyb3MgeSBlbiBlbCBlamUgKnoqIG9ic2VydmFtb3MgZWwgdmFsb3IgZGVsIGRlbCBlcnJvciBjdWFkcmFjdGljbyBtZWRpbyAoRUNNKS4KCk5vdGVtb3MgcXVlIHlhIG5vIGVzdGFtb3MgdHJhYmFqYW5kbyBjb24gbGEgZGlzdGFuY2lhIHNpbm8gcXVlIGVzdGFtb3MgZ3JhZmljYW5kbyBsYSBzdXBlcmZpY2llIGRlbCBFQ00gY29tbyBmdW5jacOzbiBkZSBhbWJvcyBwYXJhbWV0cm9zLgoKUG9yIGxhIGbDs3JtdWxhIGRlbCBFQ00gZXN0YSBzdXBlcmZpY2llIGVzIGNvbnZleGEgeSBwcmVzZW50YSB1biBtw61uaW1vIGdsb2JhbC4KCmBgYHtyLCBlY2hvPUZBTFNFfQojIE1vZGVsbyBsaW5lYWwKbW9kZWxfcHJlZGljdGlvbnMgPC0gZnVuY3Rpb24ocGFyYW1ldGVycywgZGF0YSwgcHJlZGljdG9yKXsKICAgcHJlZCA8LSBwYXJhbWV0ZXJzWzFdICsgcGFyYW1ldGVyc1syXSAqIGRhdGFbW3ByZWRpY3Rvcl1dCiAgIHJldHVybihwcmVkKQp9CgojIENhbGN1bGFyIGVsIHJzcwpnZXRfcnNzIDwtIGZ1bmN0aW9uKHBhcmFtZXRlcnMsIGRhdGEsIHByZWRpY3RvciA9ICd4JywgcHJlZGljdGVkID0gJ3knKXsKICBwcmVkaWN0aW9uIDwtIG1vZGVsX3ByZWRpY3Rpb25zKHBhcmFtZXRlcnMsIGRhdGEsIHByZWRpY3RvciA9IHByZWRpY3RvcikKICByZXNpZHVhbHMgPC0gZGF0YVtbcHJlZGljdGVkXV0gLSBtb2RlbF9wcmVkaWN0aW9ucyhwYXJhbWV0ZXJzLCBkYXRhLCAneCcpICAKICByc3MgPC0gc3VtKChyZXNpZHVhbHMpXjIpCiAgcmV0dXJuKHJzcykKfQoKI0NhbGN1bGFyIGVsIHJzcyBwYXJhIGVsIGRhdGFzZXQgc2ltMQpzaW0xX2dldF9yc3MgPC0gZnVuY3Rpb24oYTAsIGExKSB7CiAgZ2V0X3JzcyhjKGEwLCBhMSksIHNpbTEpCn0KCiMgVmVjdG9yZXMgZGUgcGFyYW1ldHJvcwpiMCA9IHNlcSgyLCA2LCBieSA9IDAuMSkKYjEgPSBzZXEoMS43LCAyLjUsIGxlbmd0aD1sZW5ndGgoYjApKQoKIyBHcmlsbGEgZGUgbW9kZWxvcwptb2RlbHNfZ3JpZCA8LSBleHBhbmQuZ3JpZCgKICAKICBiMCA9IHNlcSgyLCA2LCBieSA9IDAuMSksCiAgYjEgPSBzZXEoMS43LCAyLjUsIGxlbmd0aD1sZW5ndGgoYjEpKQopICU+JSAKICBtdXRhdGUoZGlzdCA9IHB1cnJyOjptYXAyX2RibChiMCwgYjEsIHNpbTFfZ2V0X3JzcykpIAoKCmBgYAoKYGBge3J9CiMgTWF0cml6IHBhcmEgZWwgZ3JhZmljbwpyc3NfbWF0cml4IDwtIG1hdHJpeChtb2RlbHNfZ3JpZFtbImRpc3QiXV0sbnJvdyA9IGxlbmd0aChiMSksbmNvbCA9IGxlbmd0aChiMSksIGJ5cm93ID0gVFJVRSkKCiMgR3JhZmljbyB1c2FuZG8gcGxvdGx5CnJzc19ncmFwaCA9IHBsb3RfbHkoeD1iMCwgeT1iMSwgej1yc3NfbWF0cml4KSAlPiUgYWRkX3N1cmZhY2UoY29udG91cnMgPSBsaXN0KAogIHogPSBsaXN0KAogICAgc2hvdz1UUlVFLAogICAgdXNlY29sb3JtYXA9VFJVRSwKICAgIGhpZ2hsaWdodGNvbG9yPSIjZmYwMDAwIiwKICAgIHByb2plY3Q9bGlzdCh6PVRSVUUpCiAgKQopLCByZXZlcnNlc2NhbGU9VFJVRSkgICU+JQogIGxheW91dCgKICAgIHRpdGxlID0gIlN1cGVyZmljaWUgZGVsIEVDTSIsCiAgICBzY2VuZSA9IGxpc3QoCiAgICAgIHhheGlzID0gbGlzdCh0aXRsZSA9ICJhMCIpLAogICAgICB5YXhpcyA9IGxpc3QodGl0bGUgPSAiYTEiKSwKICAgICAgemF4aXMgPSBsaXN0KHRpdGxlID0gIlJTUyIpCiAgICApKQoKcnNzX2dyYXBoCmBgYAoKIyMgw5NwdGltbyBwb3IgbcOpdG9kb3MgbnVtw6lyaWNvcyAKClBvZHLDrWFtb3MgaXIgaGFjaWVuZG8gbGEgY3VhZHLDrWN1bGEgbcOhcyBmaW5hIHkgZmluYSBoYXN0YSBxdWUgbm9zIGNlbnRyYW1vcyBlbiBlbCBtZWpvciBtb2RlbG8uIFBlcm8gaGF5IG1lam9yZXMgZm9ybWFzIGRlIGFib3JkYXIgZXNlIHByb2JsZW1hIGNvbW8gaGVycmFtaWVudGFzIGRlIG9wdGltaXphY2nDs24gbnVtw6lyaWNhcy4gQWxndW5hcyBkZSBlbGxhcyBzb246CgoqIELDunNxdWVkYSBfX05ld3Rvbi1SYXBoc29uX18uCiogKipHcmFkaWVudCBEZXNjZW50KioKCkxhIGludHVpY2nDs24gZGUgZXN0YXMgZG9zIGhlcnJhbWllbnRhcyBlcyBiYXN0YW50ZSBzaW1wbGU6IFNlIGVsaWdlIHVuIHB1bnRvIGRlIHBhcnRpZGEgZW4gbGEgc3VwZXJmaWNpZSBkZSBsYSBmdW5jacOzbiBvYmpldGl2byB5IHNlIGJ1c2NhIGxhIHBlbmRpZW50ZSBtw6FzIGluY2xpbmFkYS4gTHVlZ28sIGRlc2NpZW5kZSBwb3IgZXNhIHBlbmRpZW50ZSB1biBwb2NvLCB5IHNlIHJlcGl0ZSB1bmEgeSBvdHJhIHZleiwgaGFzdGEgYWxjYW56YXIgbGEgY29uZGljacOzbiBkZSBjb3J0ZS4gCgoKRW4gUiwgcG9kZW1vcyB1dGlsaXphciBsYSBmdW5jacOzbiBgb3B0aW0gKClgLiBDdWVudGEgY29uIGxvcyBzaWd1aWVudGVzIHBhcsOhbWV0cm9zOgoKLSAqKnBhcioqOiB2ZWN0b3IgZGUgcHVudG9zIGluaWNpYWxlcy4gRWxlZ2ltb3MgZWwgb3JpZ2VuIHBvciBwb25lciBjdWFscXVpZXIgY29zYQotICoqZm4qKjogZnVuY2nDs24gb2JqZXRpdm8sIHkgbG9zIHBhcsOhbWV0cm9zIHF1ZSBudWVzdHJhIGZ1bmNpw7NuIG5lY2VzaXRhIChkYXRhKQoKYGBge3J9CiMgQ29ycmVtb3MgbGEgb3B0aW1pemFjaW9uCmJlc3QgPC0gb3B0aW0oYygwLCAwKSwgbWVhc3VyZV9kaXN0YW5jZSwgZGF0YSA9IHNpbTEpCgpiZXN0CmBgYAoKCmBgYHtyfQojIE9idGVuZW1vcyBsb3MgbWVqb3JlcyBwYXJhbWV0cm9zCmJlc3QkcGFyCgojIEdyYWZpY2Ftb3MgbGEgbGluZWEgZGUgbG9zIG1lam9yZXMgcGFyYW1ldHJvcwpnZ3Bsb3Qoc2ltMSwgYWVzKHgsIHkpKSArIAogIGdlb21fcG9pbnQoc2l6ZSA9IDIsIGNvbG91ciA9ICJncmV5MzAiKSArIAogIGdlb21fYWJsaW5lKGludGVyY2VwdCA9IGJlc3QkcGFyWzFdLCBzbG9wZSA9IGJlc3QkcGFyWzJdLCBjb2xvcj0iZmlyZWJyaWNrIikgKwogIHRoZW1lX2J3KCkKYGBgCgoK